#pragma once
#include<iostream>
using namespace std;


enum Colour {
	RED,
	BLACK
};

template <class K, class V>
struct RBTreeNode {
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;

	Colour _Col;

	pair<K, V> _kv;

	RBTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _Col(RED)
		, _kv(kv)
	{}
};

template <class K, class V>
class RBTree {
	typedef RBTreeNode<K, V> Node;


public:
	RBTree()
		:_root(nullptr)
	{}
	~RBTree() {
		_Destroy(_root);
	}

	pair<Node*, bool> Insert(const pair<K, V>& kv) {
		//先按照二叉搜索树的插入方式把节点插入到红黑树

		//根节点为空
		if (_root == nullptr) {
			_root = new Node(kv);
			//根节点必须是黑色
			_root->_Col = BLACK;
			return make_pair(_root, true);
		}

		//根节点不为空 

		Node* parent = nullptr;
		Node* cur = _root;

		while (cur) {
			if (cur->_kv.first > kv.first) {
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_kv.first < kv.first) {
				parent = cur;
				cur = cur->_right;
			}
			else {
				//节点已经存在，插入失败
				return make_pair(cur, false);
			}
		}

		//找到要插入的节点位置
		cur = new Node(kv);
		//记录插入节点的位置
		Node* newNode = cur;

		//新节点的链接关系
		if (parent->_kv.first > kv.first) {
			parent->_left = cur;
			cur->_parent = parent;
		}
		else {
			parent->_right = cur;
			cur->_parent = parent;
		}
		

		//插入新节点成功

		//检测红黑树的性质是否被破坏



		//如果cur的parent存在且为红，说明树的性质已经被破坏
		while (parent && parent->_Col == RED) {
			//这时就要看cur的uncle
			Node* grandParent = parent->_parent;
			if (parent == grandParent->_left) {
				Node* uncle = grandParent->_right;

				//情况1 cur的uncle存在且为红色
				//变色处理
				if (uncle && uncle->_Col == RED) {
					parent->_Col = BLACK;
					uncle->_Col = BLACK;
					grandParent->_Col = RED;

					cur = grandParent;
					parent = cur->_parent;
				}

				//情况2 cur的uncle存在且为黑 
				//说明cur不是新增节点，cur是情况1迭代上来的
				//情况3 cur的uncle不存在 可以和情况2合并
				//进行右单旋 变色
				else{
					//祖孙三代在一条直线
					if (parent->_left == cur) {
						//右单旋
						_RotateR(grandParent);
						//变色
						parent->_Col = BLACK;
						grandParent->_Col = RED;
					}
					else { //parent->_right == cur
						//左单旋
						_RotateL(parent);

						//右单旋
						_RotateR(grandParent);
						//变色
						grandParent->_Col = RED;
						cur->_Col = BLACK;
					}

					break;
					//旋转完后，调整完成，不用再向上调整
				}
			}
			//parent == grandParent->_right
			else {
				Node* uncle = grandParent->_left;
				//uncle为红 变色
				if (uncle && uncle->_Col == RED) {
					uncle->_Col = BLACK;
					parent->_Col = BLACK;
					grandParent->_Col = RED;

					//继续向上检测
					cur = grandParent;
					parent = cur->_parent;
				}
				//uncle为黑或者uncle不存在
				else {
					//祖孙三代在一条直线
					if (parent->_right == cur) {
						//左单旋
						_RotateL(grandParent);
						//变色
						grandParent->_Col = RED;
						parent->_Col = BLACK;
					}
					//祖孙三代不在一条直线
					else {
						_RotateR(parent);
						_RotateL(grandParent);

						//变色
						grandParent->_Col = RED;
						cur->_Col = BLACK;
					}

					//旋转完结束
					break;
				}
			}
		}


		//插入成功
		//把红黑树的根节点变成黑色
		_root->_Col = BLACK;
		return make_pair(newNode, true);
	}




	Node* Find(const K& key) {
		if (_root == nullptr)
			return nullptr;

		Node* cur = _root;

		while (cur) {
			if (cur->_kv.first > key) {
				cur = cur->_left;
			}
			else if (cur->_kv.first < key) {
				cur = cur->_right;
			}
			else {
				//找到了
				return cur;
			}
		}

		//没找到
		return nullptr;
	}


	bool IsRBTree() {
		if (_root == nullptr)
			return true;

		if (_root->_Col == RED) {
			cout << "根节点为红色" << endl;
			return false;
		}
			

		//计算一个路径黑色节点的标准值
		Node* cur = _root;

		int BlackNum = 0;

		while (cur) {
			if (cur->_Col == BLACK)
				BlackNum++;

			cur = cur->_left;
		}

		int count = 0;

		return _IsRBTree(_root, BlackNum, count);
	}

	void InOrder() {
		_InOrder(_root);
	}

private:

	void _RotateL(Node* parent) {
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* grandParent = parent->_parent;

		parent->_right = subRL;
		if (subRL) {
			subRL->_parent = parent;
		}

		subR->_left = parent;
		parent->_parent = subR;

		if (parent == _root) {
			_root = subR;
			subR->_parent = nullptr;
		}
		else {
			if (grandParent->_left == parent) {
				grandParent->_left = subR;
			}
			else {
				grandParent->_right = subR;
			}
			subR->_parent = grandParent;
		}
	}


	//右单旋
	void _RotateR(Node* parent) {
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* grandParent = parent->_parent;

		parent->_left = subLR;
		//subLR有可能为空
		if (subLR) {
			subLR->_parent = parent;
		}

		subL->_right = parent;
		parent->_parent = subL;


		//看要旋转的点是子树还是根
		if (parent == _root) {
			_root = subL;
			subL->_parent = nullptr;
		}
		else {
			if (grandParent->_left == parent) {
				grandParent->_left = subL;
			}
			else {
				grandParent->_right = subL;
			}
			subL->_parent = grandParent;
		}

	}


	bool _IsRBTree(Node* root, int BlackNum, int count) {
		
		//找到了路径结束
		if (root == nullptr) {
			if (count != BlackNum) {
				//有一条路径黑色节点数量和最左路径不相等
				cout << "有一条路径黑色节点数量和最左路径不相等" << endl;
				return false;
			}
			return true;
		}

		//检测红色节点的父节点是否是红色节点
		if (root->_Col == RED && root->_parent->_Col == RED) {
			cout << "有两个连续的红色节点" << endl;
			return false;
		}

		//如果节点是黑色 ++count
		if (root->_Col == BLACK)
			count++;

		return _IsRBTree(root->_left, BlackNum, count)
			&& _IsRBTree(root->_right, BlackNum, count);
	}


	void _InOrder(Node* root) {
		if (root == nullptr)
			return;

		_InOrder(root->_left);

		cout << root->_kv.first << " : " << root->_kv.second << endl;
		_InOrder(root->_right);
	}


	void _Destroy(Node* root) {
		if (root == nullptr)
			return;

		_Destroy(root->_left);
		_Destroy(root->_right);

		delete root;
	}

private:
	Node* _root;
};